import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class project {
    public String evaluate(String s, List<List<String>> knowledge) {
        int len=s.length();
        Map<String,String> map=new HashMap<>();
        for(List<String> list : knowledge){
            map.put(list.get(0),list.get(1));
        }
        String ret="";
        for(int i=0;i<len;i++){
            char ch=s.charAt(i);
            StringBuilder sb=new StringBuilder();
            if(ch=='('){
                while (i<len){
                    i++;
                    ch=s.charAt(i);
                    if(ch==')'){
                        break;
                    }
                    sb.append(ch);
                }
                if(map.containsKey(sb.toString())){
                    ret+=map.get(sb.toString());
                }else{
                    ret+='?';
                }
            }else{
                ret+=ch;
            }
        }
        return ret;
    }

















    public int minCost(String colors, int[] neededTime) {
        int len=colors.length();
        int sum=0;
        for(int i=0;i<len;i++){
            char ch=colors.charAt(i);
            int max=neededTime[i];
            sum+=neededTime[i];
            while (i<len-1&&ch==colors.charAt(i+1)){
                max=Math.max(max,neededTime[i+1]);
                sum+=neededTime[i+1];
                i++;
            }
            sum-=max;
        }
        return sum;
    }




















    public int minDays(int[] bloomDay, int m, int k) {
        if(bloomDay.length<m*k){
            return -1;
        }
        int left=Integer.MAX_VALUE;
        int right=0;
        for(int num : bloomDay){
            left=Math.min(left,num);
            right=Math.max(right,num);
        }
        while (left<right){
            int mid=left+(right-left)/2;
            if(flower(bloomDay,mid,m,k)){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
    public boolean flower(int[] arr,int mid,int m,int k){
        int count=0;
        int continuity=0;
        for(int num : arr){
            if(num<=mid){
                continuity++;
                if(continuity==k){
                    count++;
                    continuity=0;
                }
            }else{
                continuity=0;
            }
            if(count>=m){
                return true;
            }
        }
        return false;
    }










    public List<String> printVertically(String s) {
        String[] str=s.split(" ");
        List<String> list=new LinkedList<>();
        int index=0;
        while (true){
            StringBuilder sb = new StringBuilder();
            for (String node : str) {
                if (index < node.length()) {
                    sb.append(node.charAt(index));
                } else {
                    sb.append(' ');
                }
            }
            for(int i=str.length-1;i>=0;i--){
                if(sb.charAt(i)==' '){
                    sb.deleteCharAt(i);
                }else{
                    break;
                }
            }
            if(sb.length()==0){
                break;
            }
            list.add(sb.toString());
            index++;
        }
        return list;
    }




















    public int findMinFibonacciNumbers(int k) {
        List<Integer> list=new LinkedList<>();
        int a=1;
        int b=1;
        list.add(a);
        list.add(b);
        while (a+b<k){
            int tmp=a+b;
            list.add(tmp);
            a=b;
            b=tmp;
        }
        int count=0;
        for(int i=list.size();i>=0;i--){
            if(k==0){
                break;
            }
            if(list.get(i)<=k){
                k-=list.get(i);
                count++;
            }
        }
        return count;
    }
}
